import java.util.HashMap;
import java.util.Map;

public class GeoHash {

    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

    /**
     * Encodes latitude/longitude to geohash.
     *
     * @param lat       Latitude in degrees.
     * @param lon       Longitude in degrees.
     * @param precision Number of characters in resulting geohash.
     * @return Geohash of supplied latitude/longitude.
     */
    public static String encode(double lat, double lon, int precision) {
        if (precision <= 0) throw new IllegalArgumentException("Invalid precision");

        StringBuilder geohash = new StringBuilder();
        boolean evenBit = true;
        int bit = 0;
        int idx = 0;

        double latMin = -90, latMax = 90;
        double lonMin = -180, lonMax = 180;

        while (geohash.length() < precision) {
            if (evenBit) {
                double lonMid = (lonMin + lonMax) / 2;
                if (lon >= lonMid) {
                    idx = idx * 2 + 1;
                    lonMin = lonMid;
                } else {
                    idx = idx * 2;
                    lonMax = lonMid;
                }
            } else {
                double latMid = (latMin + latMax) / 2;
                if (lat >= latMid) {
                    idx = idx * 2 + 1;
                    latMin = latMid;
                } else {
                    idx = idx * 2;
                    latMax = latMid;
                }
            }
            evenBit = !evenBit;

            if (++bit == 5) {
                geohash.append(BASE32.charAt(idx));
                bit = 0;
                idx = 0;
            }
        }

        return geohash.toString();
    }

    /**
     * Decodes geohash to latitude/longitude.
     *
     * @param geohash Geohash string to be converted.
     * @return Center of the geohashed location as a Map with keys "lat" and "lon".
     */
    public static Map<String, Double> decode(String geohash) {
        if (geohash == null || geohash.isEmpty()) throw new IllegalArgumentException("Invalid geohash");

        double[] latRange = {-90, 90};
        double[] lonRange = {-180, 180};
        boolean evenBit = true;

        for (char c : geohash.toCharArray()) {
            int idx = BASE32.indexOf(c);
            if (idx == -1) throw new IllegalArgumentException("Invalid geohash character: " + c);

            for (int n = 4; n >= 0; n--) {
                int bitN = (idx >> n) & 1;
                if (evenBit) {
                    double lonMid = (lonRange[0] + lonRange[1]) / 2;
                    if (bitN == 1) {
                        lonRange[0] = lonMid;
                    } else {
                        lonRange[1] = lonMid;
                    }
                } else {
                    double latMid = (latRange[0] + latRange[1]) / 2;
                    if (bitN == 1) {
                        latRange[0] = latMid;
                    } else {
                        latRange[1] = latMid;
                    }
                }
                evenBit = !evenBit;
            }
        }

        double lat = (latRange[0] + latRange[1]) / 2;
        double lon = (lonRange[0] + lonRange[1]) / 2;

        Map<String, Double> result = new HashMap<>();
        result.put("lat", lat);
        result.put("lon", lon);
        return result;
    }

    /**
     * Determines adjacent cell in the given direction.
     *
     * @param geohash  Cell to which adjacent cell is required.
     * @param direction Direction from geohash ("n", "s", "e", "w").
     * @return Geohash of the adjacent cell.
     */
    public static String adjacent(String geohash, String direction) {
        if (geohash == null || geohash.isEmpty() || direction == null || direction.isEmpty()) {
            throw new IllegalArgumentException("Invalid geohash or direction");
        }

        direction = direction.toLowerCase();
        if (!"nsew".contains(direction)) throw new IllegalArgumentException("Invalid direction");

        final String[][] neighbour = {
                {"p0r21436x8zb9dcf5h7kjnmqesgutwvy", "bc01fg45238967deuvhjyznpkmstqrwx"},
                {"14365h7k9dcfesgujnmqp0r2twvyx8zb", "238967debc01fg45kmstqrwxuvhjyznp"},
                {"bc01fg45238967deuvhjyznpkmstqrwx", "p0r21436x8zb9dcf5h7kjnmqesgutwvy"},
                {"238967debc01fg45kmstqrwxuvhjyznp", "14365h7k9dcfesgujnmqp0r2twvyx8zb"}
        };

        final String[][] border = {
                {"prxz", "bcfguvyz"},
                {"028b", "0145hjnp"},
                {"bcfguvyz", "prxz"},
                {"0145hjnp", "028b"}
        };

        int dirIdx = "nsew".indexOf(direction);
        char lastChar = geohash.charAt(geohash.length() - 1);
        String parent = geohash.substring(0, geohash.length() - 1);
        int type = geohash.length() % 2;

        if (border[dirIdx][type].indexOf(lastChar) != -1 && !parent.isEmpty()) {
            parent = adjacent(parent, direction);
        }

        return parent + BASE32.charAt(neighbour[dirIdx][type].indexOf(lastChar));
    }

    /**
     * Returns all 8 adjacent cells to the specified geohash.
     *
     * @param geohash Geohash neighbours are required of.
     * @return Map of 8 adjacent cells with directions as keys ("n", "ne", "e", etc.).
     */
    public static Map<String, String> neighbours(String geohash) {
        Map<String, String> result = new HashMap<>();
        result.put("n", adjacent(geohash, "n"));
        result.put("ne", adjacent(adjacent(geohash, "n"), "e"));
        result.put("e", adjacent(geohash, "e"));
        result.put("se", adjacent(adjacent(geohash, "s"), "e"));
        result.put("s", adjacent(geohash, "s"));
        result.put("sw", adjacent(adjacent(geohash, "s"), "w"));
        result.put("w", adjacent(geohash, "w"));
        result.put("nw", adjacent(adjacent(geohash, "n"), "w"));
        return result;
    }

}
